package top.ivansong92.example.leetcode.learning.data.struct.tree;


import org.junit.Test;

import java.util.*;

public class TestExample {
    /**
     * Definition for a binary tree node.
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 二叉树的最大深度
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/47/
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDep = depth(root.left, 1);
        int rightDep = depth(root.right, 1);
        return Math.max(leftDep, rightDep);
    }

    private int depth(TreeNode node, int len) {
        if (node == null) {
            return len;
        }
        len++;
        int leftLen = depth(node.left, len);
        int rightLen = depth(node.right, len);
        return Math.max(leftLen, rightLen);
    }

    /**
     * 验证二叉搜索树
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/48/
     */

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) {
            return true;
        }


        if (left == null) {
            if (right.val <= root.val) {
                return false;
            }

            return isValidBST(right.left, right.val, root.val) && isValidBST(right.right, null, right.val);
        }

        if (right == null) {
            if (left.val >= root.val) {
                return false;
            }

            return isValidBST(left.left, left.val, null) && isValidBST(left.right, root.val, left.val);
        }

        return isValidBST(left, root.val, null) && isValidBST(right, null, root.val);
    }


    private boolean isValidBST(TreeNode node, Integer maxVal, Integer minVal) {
        if (node == null) {
            return true;
        }

        if (maxVal != null && maxVal.compareTo(node.val) <= 0) {
            return false;
        }
        if (minVal != null && minVal.compareTo(node.val) >= 0) {
            return false;
        }

        return isValidBST(node.left, node.val, minVal) && isValidBST(node.right, maxVal, node.val);

    }

    /**
     * 617. 合并二叉树
     *
     * @param root1
     * @param root2
     * @return
     */

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        return doMerge(root1, root2);
    }

    private TreeNode doMerge(TreeNode tree1Node, TreeNode tree2Node) {
        if (tree1Node == null && tree2Node == null) {
            return null;
        }

        TreeNode node;
        if (tree1Node != null && tree2Node != null) {
            node = new TreeNode(tree1Node.val + tree2Node.val);
        } else if (tree1Node != null) {
            node = new TreeNode(tree1Node.val);
        } else {
            node = new TreeNode(tree2Node.val);
        }

        node.left = doMerge(tree1Node != null ? tree1Node.left : null, tree2Node != null ? tree2Node.left : null);
        node.right = doMerge(tree1Node != null ? tree1Node.right : null, tree2Node != null ? tree2Node.right : null);
        return node;
    }


    /**
     * 100. 相同的树
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return doMatch(p, q);
    }

    public boolean doMatch(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 == null || node2 == null) {
            return false;
        } else {
            return node1.val == node2.val && doMatch(node1.left, node2.left) && doMatch(node1.right, node2.right);
        }
    }


    /**
     * 145. 二叉树的后序遍历
     *
     * @param root
     * @return
     */

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        doTraversal(root, res);
        return res;
    }

    private void doTraversal(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            list.add(node.val);
            return;
        }
        doTraversal(node.left, list);
        doTraversal(node.right, list);
        list.add(node.val);
    }

    /**
     * 144. 二叉树的前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        doPreorderTra(res, root);
        return res;
    }

    private void doPreorderTra(List<Integer> list, TreeNode node) {
        if (node == null) {
            return;
        }

        list.add(node.val);
        doPreorderTra(list, node.left);
        doPreorderTra(list, node.right);
    }

    /**
     * 94. 二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> res = new ArrayList<>();
        doInorderTra(res, root);
        return res;
    }

    private void doInorderTra(List<Integer> list, TreeNode node) {
        if (node == null) {
            return;
        }

        doPreorderTra(list, node.left);
        list.add(node.val);
        doPreorderTra(list, node.right);
    }

    /**
     * 107. 二叉树的层序遍历 II
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }


        List<List<Integer>> list = new ArrayList<>();
        doSearchLevelOrder(root, 0, list);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

    private void doSearchLevelOrder(TreeNode node, int level, List<List<Integer>> list) {
        if (list.size() <= level) {
            for (int i = list.size(); i <= level; i++) {
                list.add(new ArrayList<>());
            }
        }

        list.get(level).add(node.val);
        if (node.left != null) {
            doSearchLevelOrder(node.left, level + 1, list);
        }

        if (node.right != null) {
            doSearchLevelOrder(node.right, level + 1, list);
        }
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }


        List<List<Integer>> list = new ArrayList<>();
        doZigzagSearchLevelOrder(root, 0, list);
        return list;
    }

    private void doZigzagSearchLevelOrder(TreeNode node, int level, List<List<Integer>> list) {
        if (node == null) {
            return;
        }
        if (list.size() <= level) {
            for (int i = list.size(); i <= level; i++) {
                list.add(new ArrayList<>());
            }
        }

        boolean dub = level % 2 == 0;
        if (dub) {
            list.get(level).add(node.val);
        } else {
            list.get(level).add(0, node.val);
        }

        doZigzagSearchLevelOrder(node.left, level + 1, list);
        doZigzagSearchLevelOrder(node.right, level + 1, list);
    }


    /**
     * 199. 二叉树的右视图
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }


        List<List<Integer>> list = new ArrayList<>();
        doSearchNode(root, 0, list);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            List<Integer> val = list.get(i);
            res.add(val.get(val.size() - 1));
        }
        return res;
    }

    private void doSearchNode(TreeNode node, int level, List<List<Integer>> list) {
        if (list.size() <= level) {
            for (int i = list.size(); i <= level; i++) {
                list.add(new ArrayList<>());
            }
        }

        list.get(level).add(node.val);
        if (node.left != null) {
            doSearchNode(node.left, level + 1, list);
        }

        if (node.right != null) {
            doSearchNode(node.right, level + 1, list);
        }
    }

    /**
     * 226. 翻转二叉树
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        doInvert(root);
        return root;
    }

    private void doInvert(TreeNode node) {
        if (node == null) {
            return;
        }

        TreeNode left = node.left;
        node.left = node.right;
        node.right = left;
        doInvert(node.right);
        doInvert(node.left);
    }


    /**
     * 111. 二叉树的最小深度
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        } else if (root.left == null) {
            return getMinDep(root.right, 1);
        } else if (root.right == null) {
            return getMinDep(root.left, 1);
        } else {
            return Math.min(getMinDep(root.left, 1), getMinDep(root.right, 1));
        }
    }

    private int getMinDep(TreeNode node, int len) {
        if (node.right == null && node.left == null) {
            return len + 1;
        }

        len++;
        Integer leftLen = null, rightLen = null;
        if (node.left != null) {
            leftLen = getMinDep(node.left, len);
        }

        if (node.right != null) {
            rightLen = getMinDep(node.right, len);
        }

        if (leftLen == null) {
            return rightLen;
        }

        if (rightLen == null) {
            return leftLen;
        }

        return Math.min(leftLen, rightLen);
    }


    /**
     * 101. 对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        } else if (root.left == null || root.right == null) {
            return false;
        } else {
            return symmetricMatch(root.left, root.right);
        }
    }

    private boolean symmetricMatch(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            return left.val == right.val && symmetricMatch(left.left, right.right) &&
                    symmetricMatch(right.left, left.right);
        }
    }

    @Test
    public void test1() {
        String s = "[1,2,2,null,3,null,3]";
        TreeNode node = stringToTreeNode(s);
        System.out.println(isSymmetricV2(node));

    }

    public boolean isSymmetricV2(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        if (root.right != null && root.left == null) {
            return false;
        }

        if (root.right == null) {
            return false;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root.left);
        queue.addLast(root.right);
        TreeNode left, right;
        while (queue.size() > 1) {
            left = queue.removeFirst();
            right = queue.removeFirst();
            if (left.val != right.val) {
                return false;
            }

            if (left.left != null && right.right != null) {
                queue.addLast(left.left);
                queue.addLast(right.right);
            } else if (left.left == null && right.right != null) {
                return false;
            } else if (left.left != null) {
                return false;
            }

            if (left.right != null && right.left != null) {
                queue.addLast(right.left);
                queue.addLast(left.right);
            } else if (left.right == null && right.left != null) {
                return false;
            } else if (left.right != null) {
                return false;
            }
        }

        return queue.isEmpty();
    }


    @Test
    public void test2() {
        String s = "[1,2,2,null,3,null,3]";
        TreeNode node = stringToTreeNode(s);
        System.out.println(countNodes(node));

    }

    /**
     * 222. 完全二叉树的节点个数
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        return getNodesNum(root);
    }

    private int getNodesNum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        if (node.right == null && node.left == null) {
            return 1;
        }

        int num = 1;
        if (node.left != null) {
            num += getNodesNum(node.left);
        }
        if (node.right != null) {
            num += getNodesNum(node.right);
        }
        return num;
    }


    /**
     * 110. 平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) >= 0;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getHeight(node.left), right = getHeight(node.right);
        if (left >= 0 && right >=0 && Math.abs(left - right) <= 1) {
            return Math.max(left, right) + 1;
        } else {
            return -1;
        }
    }



    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }

    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }
}
